package com.zt.java.back;

public class MaxHeapSort {
    public static void main(String args[]){
        int a[] = {3,5,1,6,9,4,8,12};
        MaxHeapSort sort = new MaxHeapSort();
        //1.建堆
        sort.buildMaxHeap(a);
        sort.print(a);
        //2.排序
        sort.heapSort(a);
        //3.输出
        sort.print(a);

    }
    public void print(int a[]){
        System.out.println();
        for (int value: a) {
            System.out.print(value+" ");
        }
    }
    public void buildMaxHeap(int a[]){
        int heapSize = a.length;
        //从最大的非叶子节点开始调整
        for(int i=heapSize/2-1; i>=0; i--){
            adjustMaxHeap(a,i,heapSize);
        }
    }
    public void adjustMaxHeap(int a[],int i,int heapSize){
        int left = i*2 + 1;
        int right = i*2 + 2;
        int maxIndex = i;
        if(left <heapSize && a[left]>a[i]){
            maxIndex = left;
        }else {
            maxIndex = i;
        }
        if(right <heapSize && a[right] >a[maxIndex]){
            maxIndex = right;
        }
        if(maxIndex!=i){
            swap(a,i,maxIndex);
            adjustMaxHeap(a,maxIndex,heapSize);
        }
    }
    public void heapSort(int a[]){
        int heapsize = a.length;
        int n = a.length;
        for(int i=n;i>1;i--){
            swap(a,0,i-1);
            heapsize--;
            adjustMaxHeap(a,0,heapsize);
        }
    }

    public void swap(int a[],int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
